Problem statement: zenit16ckg

Génius

Počet bodov: 25, časový limit: 1000ms

Taký génius to má ťažké. Stále mu po rozume chodia prapodivné myšlienky, z nich vyplývajú zložité otázky, a tie si vyžadujú komplexné riešenia. Nikto mu však nikdy nechce pomôcť hľadať odpovede bez toho, aby mu predtým vysvetlil, prečo vlastne rieši svoj čudesný problém.

Našťastie istý génius zistil, že niektorým osobám praktické vysvetlenie netreba. Stačí im sľúbiť dosť veľa súťažných bodov, a bez rozmyslu mu pomôžu vyriešiť hocaký nezmyselný problém.

Problém je teda nasledovný: Číslo génius volá ‘modré’, ak sa v ňom vyskytuje každá číslica od 0 po 9 práve raz. Génius volá číslo ‘tyrkysové’, ak ľubovoľný jeho prefix je deliteľný dĺžkou zvoleného prefixu. Číslo génius považuje za ‘náramne dôležité,’ ak je súčasne modré aj tyrkysové.

Napríklad, ak by génius volal číslo ‘modré’, ak sa v ňom vyskytuje každá číslica od 1 po 6 práve raz, tak by považoval číslo \(123654\) za náramne dôležité, pretože \(123654\) je deliteľné šiestimi, \(12365\) je deliteľné piatimi, \(1236\) je deliteľné štyrmi, …, \(1\) je deliteľné jednotkou.

Úloha

Génius potrebuje rýchlo zistiť počet náramne dôležitých čísel v niekoľkých intervaloch. Nepovie vám, na čo je to dobré, ale sľubuje vám 25 súťažných bodov, ak mu pomôžete.

Vstup a výstup

V prvom riadku vstupu je číslo \(1 \leq t \leq 10^5\): počet géniových otázok. Nasleduje \(t\) riadkov s číslami \(1 \leq a \leq b \leq 10^{18}\).

Pre každú dvojicu \(a \leq b\) vypíšte, koľko náramne dôležitých čísel je v intervale \([a,b]\)¹.

 Príklad

Input:

1
3798552315 3817006413

Output:

1